
#procedure BellmanFord(list vertices, list edges, vertex source)
#    for each vertex v in vertices:
#        if v is source then distance[v] := 0
#        else distance[v] := infinity
#        predecessor[v] := null
#
#    for i from 1 to size(vertices) -1:
#        for each edge (u,v) with weight w in deges:
#            if distance[u] + w < distance[v]:
#                distance[v] := distance[u] + w
#                predecessor[v] := u
#
#    for each edge (u, v) with weight w in edges:
#        if distance[u] + w < distance[v]:
#            error
#


def bellmanford(vertices,edges,source):
    pass


# 图论数据结构
# 邻接矩阵
# 邻接表

# 邻接矩阵遍历边
# 邻接表遍历边



#邻接矩阵版本
def bellmanford(vecmatrix,source):
    predecessor = [-1 for i in range(len(vecmatrix))]
    # -1 null
    distance = [0 if i == source else 999999 for i in range(len(vecmatrix))]
    # 999999 inf

    #for i in range(len(vecmatrix)):
    #    for j in vecmatrix[source]:
    #        if distance[u] + j < distance[v]:
    #            distance[v] = distance[u] + j
    #            predecessor[v] = u
    #            source = u
    for k in range(len(vecmatrix)):
        for i,j in zip(range(len(vecmatrix)),range(len(vecmatrix))):
            if vecmatrix[i][j] != -1 : # 无连通路径
                pass
            else:
                if distance[i] + vecmatrix[i][j] < distance[j]:
                    distance[j] = distance[i] + vecmatrix[i][j]
                    predecessor[j] = i
        
    for i,j in zip(range(len(vecmatrix)),range(len(vecmatrix))):
        if vecmatrix[i][j] != -1 : # 无连通路径
            pass
        else:
            if distance[i] + j < distance[j]:
                return error
    return predecessor,distance
